package com.hy.greedy;

public class JumpGame2 {


    /**
     * 45.跳跃游戏II
     * 力扣题目链接
     *
     * 给定一个非负整数数组，你最初位于数组的第一个位置。
     *
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     *
     * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     *
     * 示例:
     *
     * 输入: [2,3,1,1,4]
     * 输出: 2
     * 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
     * 说明: 假设你总是可以到达数组的最后一个位置。
     *
     *
     * @param num
     * @return
     */
    // 1. 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
    // 2. 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。
    public int jumpGame(int [] num){
        if (num == null || num.length == 0 || num.length == 1) {
            return 0;
        }
        // 当前覆盖最远距离下标
        int currentDistance = 0;
        // 记录跳跃的次数
        int count = 0;
        // 最大的覆盖区域
        int maxDistance = 0;
        for (int i = 0; i < num.length; i++) {
            //在可覆盖区域内更新最大的覆盖区域
            maxDistance = Math.max(i+num[i],maxDistance);
            //说明当前一步，再跳一步就到达了末尾
            if (maxDistance >= num.length -1){
                count++;
                break;
            }
            //走到当前覆盖的最大区域时，更新下一步可达的最大区域
            if (i == currentDistance){
                currentDistance = maxDistance;
                count++;
            }

        }
        return count;
    }
    // 移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。
    public int jump2(int [] num){
        // 计数
        int result =0;
        // 当前距离最远距离的下标
        int end = 0;
        // 下一步覆盖的最远距离下标
        int temp = 0;
        for (int i = 0; i <= end && end < num.length - 1; ++i) {
            temp = Math.max(temp,i+num[i]);
            if (i == end){
                end = temp;
                result++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        JumpGame2 jumpGame2 = new JumpGame2();
        int [] num = {2,3,1,1,4};
        System.out.println("res: "+jumpGame2.jumpGame(num));
        System.out.println("res: "+jumpGame2.jump2(num));

    }
}
